package bm11;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/8/4 22:32
 * BM11 链表相加
 * https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b?tpId=295&tqId=1008772&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 */
public class Solution {

    // 先将两个链表反转后再相加后反转
    public ListNode addInList (ListNode head1, ListNode head2) {
        head1 = reverseList(head1);
        head2 = reverseList(head2);
        ListNode muteNode = new ListNode(-1); // 定义相加链表的辅助头节点
        ListNode cur = muteNode; // 辅助指针
        int carry = 0; // 表示进位
        while (head1 != null || head2 != null) {
            int val = carry;
            // 当链表不为空时, 则需要加上当前节点的值
            if (head1 != null) {
                val += head1.val;
                head1 = head1.next;
            }
            if (head2 != null) {
                val += head2.val;
                head2 = head2.next;
            }
            carry = val / 10;
            val = val % 10;
            ListNode newNode = new ListNode(val);
            cur.next = newNode;
            cur = cur.next;
        }
        // 处理进位
        if (carry != 0) {
            ListNode newNode = new ListNode(carry);
            cur.next = newNode;
        }
        // 反转相加的链表后返回
        return reverseList(muteNode.next);
    }

    // 反转链表
    private ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = curNext;
        }
        return pre;
    }


    private class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
            this.val = val;
        }
    }
}
